package seqlist;

/**
 * @author shkstart
 * @create 2022-08-09-23:44
 */


//车厢类
class Node{
//    存储具体元素
    int data;

//    存储下一个节点地址
    Node next;

    public Node(int data) {
        this.data = data;
    }

    public Node(int data, Node next) {
        this.data = data;
        this.next = next;
    }
}

//火车
public class SingleLinkedList {

//    当前火车的车厢个数（实际存储的数据个数）
    private int size;
//    当前火车的第一个节点
    private Node head;

//    在火车头部添加元素
    public void addFirst(int data){
//        要使用addFirst向火车中添加节点，要判断当前火车是否为空
//        -》一个节点都没有
//        要插入的就是第一节点
        Node node = new Node(data);
        if(size==0){
            head = node;
        }else{
//            当前火车存在节点
            node.next = head;
            head = node;
        }
        size++;
    }

    //    在火车尾部添加元素
    public void addLast(int data){
        addIndex(size,data);
    }

    //    在火车任意节点添加元素
    public void addIndex(int index,int data){
        //边界条件
        if(index<0||index>size){
            System.err.println("非法");
            return;
        }
        if(index==0){
            addFirst(data);
            return;
        }else{
            Node perv = head;//临时存储Head
            for (int i = 0; i < index - 1; i++) {
//                此时，perv从头走了index-1步，perv指向index-1节点
                perv = perv.next;
            }
//            此时，index处于中间位置（包含最后位置）
//            perv指向当前插入index的前驱节点
            Node node = new Node(data);
            node.next = perv.next;
            perv.next = node;
            size++;
        }
    }

    /**
     * 查询指定index位置的节点
     * @param index
     * @return
     */
    public int get(int  index){
        if(rangeCheck(index)){
            Node perv = head;
            for (int i = 0; i < index; i++) {
                perv= perv.next;
            }
            return perv.data;
        }else {
            System.err.println("非法");
            return  -1;
        }


    }

    /**
     * 查询链表中是否存在元素data
     * @param data
     * @return
     */
    public boolean contains(int data){
        Node node = head;
        while (node!=null){
            if(data == node.data){
                System.out.println("找到了指定元素");
                return  true;
            }
            node=node.next;
        }
        System.out.println("没找到");
        return false;

    }
    private boolean rangeCheck(int index){
        if(index<0||index>=size){
            return false;
        }
        return  true;
    }
    /**
     * 修改单链表中Index位置的元素，返回修改前的元素
     * @param index
     * @param data
     * @return
     */
    public int set(int index,int data){
        if(rangeCheck(index)){
            Node node = head;
            for (int i = 0; i < index; i++) {
                node= node.next;
            }
            int oldData = node.data;
            node.data = data;
            return oldData;
        }else {
            System.err.println("非法");
            return -1;
        }
    }

    public void removeFirst(){

            Node node = head;
            head = node.next;
            node.next = null;
            size--;

    }

    public void removeIndex(int index){
        if(rangeCheck(index)){
            if (index == 0) {
                removeFirst();
            }else {
                //此时删除的index是中间节点
                Node perv = head;
                for (int i = 0; i < index - 1; i++) {
                    perv = perv.next;
                }
                //此时perv是待删除节点的前驱节点
                Node node = perv.next;
                //此时node是待删除节点
                perv.next = node.next;
                //此时前后节点完成连接
                node.next=null;
                size--;
            }
        }else {
            System.err.println("非法");
        }
    }

    public void removeValueOnce(int data){
        //先要找到待删除元素的节点
        if (head.data == data) {
            removeFirst();
        }else {
            Node perv = head;
            while (perv.next!=null){
                //此时perv是待删除节点的前驱节点
                if (perv.next.data == data) {
                    //此时node节点就是待删除j节点
                    Node node = perv.next;
                    //开始删除,
                    perv.next=node.next;
                    node.next=null;
                    size--;
                    break;
                }else{
                    //此时perv不是待删除节点的前驱节点，继续遍历
                    perv=perv.next;
                }
            }
        }
    }

    public void removeValueAll(int data){

        //判断头节点
        //此时此时头节点及之后连续出现待删除元素
        while(head.data==data&&head!=null){
            removeFirst();
        }
        //此时的head一定不是待删除节点
        if (head == null) {
            //此时链表被全部删除
            return;
        }else {
//            遍历寻找待删除节点的前驱节点
            Node perv = head;
            while (perv.next != null) {
                if (perv.next.data== data){
//                    此时node就是待删除节点
                    Node node = perv.next;
                    perv.next = node.next;
                    node.next=null;
                    size--;
                }else {
                    perv = perv.next;
                }
            }
        }

    }

    public static void main(String[] args) {
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.addLast(1);
        singleLinkedList.addLast(2);
        singleLinkedList.addLast(2);
        singleLinkedList.addFirst(3);
        singleLinkedList.addFirst(2);

        System.out.println(singleLinkedList);
        singleLinkedList.removeValueAll(2);
        System.out.println(singleLinkedList);
    }
    public String toString(){
        String ret = "";
        Node node = head;
        while (node!=null){
            ret += node.data +"->";
            node = node.next;
        }
        ret += "NULL";
        return ret;
    }
}
